package one.three.thirtyFour;

import java.util.*;

public class RandomBag<Item> implements Iterable<Item> {

	private Item[] a;
	private int n;
	private final int initialSize = 10;

	public RandomBag() {
		a = (Item[]) new Object[initialSize];
	}

	public void add(Item item) {
		a[n] = item;
		n++;
		if (n > a.length / 2) {
			resize(a.length * 2);
		}
	}

	public void resize(int s) {
		Item[] temp = (Item[]) new Object[s];
		for (int i = 0; i < n; i++) {
			temp[i] = a[i];
		}
		a = temp;
	}

	private static int randomIndex(int min, int max, List<Integer> e) {
		int r = -1;
		Random random = new Random();
		do {
			r = random.nextInt(max + 1 - min);
		} while (e.contains(r + min));
		return r + min;
	}

	private void shuffle() {
		int[] ind = new int[n];
		int idx = -1;
		List<Integer> l = new ArrayList<Integer>();
		for (int i = 0; i < n; i++) {
			idx = randomIndex(0, n - 1, l);
			ind[i] = idx;
			l.add(idx);
		}

		Item[] t = (Item[]) new Object[n];
		for (int i = 0; i < n; i++) {
			t[i] = a[i];
		}
		for (int i = 0; i < n; i++) {
			a[i] = t[ind[i]];
		}

	}

	@Override
	public String toString() {
		StringBuilder s = new StringBuilder();
		for (int i = 0; i < n; i++) {
			s.append("[" + a[i] + "]");
		}
		return s.toString();
	}

	@Override
	public Iterator<Item> iterator() {

		return new RandomBagIterator<Item>();
	}

	private class RandomBagIterator<Item> implements Iterator<Item> {
		int i;

		public RandomBagIterator() {
			shuffle();
			i = 0;
		}

		@Override
		public boolean hasNext() {

			return i < n;
		}

		@Override
		public Item next() {
			Item r = (Item) a[i];
			i++;
			return r;
		}
	}

	public static void main(String[] args) {
		/*
		 * List<Integer> l = new ArrayList<Integer>(); l.add(3);
		 * System.out.println(randomIndex(2, 4, l));
		 */

		RandomBag<Integer> r = new RandomBag<Integer>();
		for (int i = 0; i < 20; i++) {
			r.add(i);
		}
		System.out.println(r);
		for (Integer i : r) {
			System.out.println(i);
		}

		/*
		 * r.shuffle(); System.out.println(r);
		 */
	}

}
